题意简述
我们有一个 点 边的无向图,有点权和边权。现在两个人将它按照自己的最优方案每次取一个点,分为两部分,求出此时他们的分差。
方法分析
边权不好处理,我们想到将它与点权合并。最容易想到的方法就是两个端点各加一半边权,这个方法也是正确的,正确性将在下方证明。
因为每个人都会按照自己的当前最优策略取,所以将整个权值排序后,编号为奇数的是一个人取的,偶数的是另一个人取的,我们只需要按照奇偶数分别算出总权值即可。
正确性证明
这里主要证明上面说的将边权与点权合并的正确性。
对于一条边 ,设两端点的初始权值为 ,我们这里将两端点的权值改为了 。
情况一: 被同一个人取到。
此时,这个人的总权值为 ,符合题意。
情况二: 被两人分别取到。
不妨设 被第一个人取到。
此时,第一个人权值为 ,第二个人权值为 。最后要将答案相减,得到 ,符合题意。
综上所述,这种方法正确。
代码与备注
在这份代码中,我们排序后按照从小到大顺序循环取值。由于题面保证 为偶数,因此这个方法也没有问题。
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
int n, m;
double a[N], s[2];
int main() {
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++) scanf("%lf", &a[i]);
for(int i=1;i<=m;i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
a[u] += w / 2.0;
a[v] += w / 2.0;
}
sort(a+1, a+1+n);
for(int i=1;i<=n;i++) s[i&1] += a[i];
printf("%.0lf\n", s[0]-s[1]);
return 0;
}